#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
    if (root == NULL) {
        return NULL;
    }

    int val = root->val;

    if (p < val && q < val) {
        return lowestCommonAncestor(root->left, p, q);
    }
    else if (p > val && q > val) {
        return lowestCommonAncestor(root->right, p, q);
    }
    else {
        return root;
    }
}

int main() {
    /*
          6
         / \
        2   8
       / \ / \
      0  4 7  9
        / \
       3   5
    */
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);

    int p, q;
    cout << "请输入两个节点的值，用空格分隔：";
    cin >> p >> q;

    TreeNode* lca = lowestCommonAncestor(root, p, q);

    if (lca != NULL) {
        cout << "节点 " << p << " 和节点 " << q << " 的最近公共祖先是：" << lca->val << endl;
    } else {
        cout << "没有找到节点 " << p << " 和节点 " << q << " 的最近公共祖先" << endl;
    }

    return 0;
}